package com.xiaoyu.linkedArray;

/**
 * @program: DS_and_A
 * @description: 删除链表的倒数第N个元素
 *
 * 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
 *
 * 进阶：你能尝试使用一趟扫描实现吗？
 *
 * 输入：head = [1,2,3,4,5], n = 2
 * 输出：[1,2,3,5]
 *
 * @author: YuWenYi
 * @create: 2021-06-01 09:31
 **/
public class RemoveNthFromEnd_19 {

    //算法通过,超越百分百,并且空间超越百分之80,是个好算法
    /*
    * 先计算链表长度len,然后根据len-n,将指针移动到要删除的位置,然后删除该结点就好了
    * */
    public static ListNode removeNthFromEnd(ListNode head, int n) {
        if (head.next==null) return null;

        int len = 0;
        ListNode p = head;
        while (p!=null){
            len++;
            p = p.next;
        }
        p = head;  //恢复p
        //将p移动到要删除的结点位置
        for (int i = 0; i < len - n; i++) {
            p = p.next;
        }

        //删除元素
        if (p.next!=null){
            p.val = p.next.val;
            p.next = p.next.next;
        }else {   //要删除的是最后一个结点
            p = head;  //恢复p
            //将p移动到要删除的结点的前一个结点的位置
            for (int i = 0; i < len - n - 1; i++) {
                p = p.next;
            }
            p.next = null; //将尾巴置空
        }
        return head;
    }

    //解法二:一遍遍历 --> 使用双指针
    public static ListNode removeNthFromEnd1(ListNode head, int n) {
        ListNode dummy = new ListNode(0,head);
        ListNode p1 = head;
        ListNode p2 = dummy;

        while (p1!=null){
            if (n != 0){
                n--;
            }else {
                p2 = p2.next;
            }
            p1 = p1.next;
        }
        p2.next = p2.next.next;

        return dummy.next;
    }

    public static void main(String[] args) {
        ListNode l1 = new ListNode(1,new ListNode(2,
                new ListNode(3,new ListNode(4,new ListNode(5)))));

        ListNode res = removeNthFromEnd1(new ListNode(1), 1);

        while (res.hasNext()){
            System.out.print(res.val+",");
            res = res.next;
        }
        System.out.println(res.val);
    }
}
